home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 7: Sunsite / Linux Cubed Series 7 - Sunsite Vol 1.iso / system / network / manageme / tcpdump-.001 / tcpdump-~ / tcpdump-3.0.2-linux / libpcap-0.0.6 / optimize.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-06-21  |  37.8 KB  |  1,924 lines
  1. /*
  2.  * Copyright (c) 1988, 1989, 1990, 1991, 1993, 1994
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that: (1) source code distributions
  7.  * retain the above copyright notice and this paragraph in its entirety, (2)
  8.  * distributions including binary code include the above copyright notice and
  9.  * this paragraph in its entirety in the documentation or other materials
  10.  * provided with the distribution, and (3) all advertising materials mentioning
  11.  * features or use of this software display the following acknowledgement:
  12.  * ``This product includes software developed by the University of California,
  13.  * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of
  14.  * the University nor the names of its contributors may be used to endorse
  15.  * or promote products derived from this software without specific prior
  16.  * written permission.
  17.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  18.  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  19.  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  20.  *
  21.  *  Optimization module for tcpdump intermediate representation.
  22.  */
  23. #ifndef lint
  24. static char rcsid[] =
  25.     "@(#) $Header: optimize.c,v 1.45 94/06/20 19:07:55 leres Exp $ (LBL)";
  26. #endif
  27.  
  28. #include <sys/types.h>
  29. #include <sys/time.h>
  30.  
  31. #include <net/bpf.h>
  32.  
  33. #include <stdio.h>
  34. #ifdef __osf__
  35. #include <stdlib.h>
  36. #include <malloc.h>
  37. #endif
  38. #include <memory.h>
  39.  
  40. #include "gencode.h"
  41.  
  42. #ifndef __GNUC__
  43. #define inline
  44. #endif
  45.  
  46. #define A_ATOM BPF_MEMWORDS
  47. #define X_ATOM (BPF_MEMWORDS+1)
  48.  
  49. #define NOP -1
  50.  
  51. /*
  52.  * This define is used to represent *both* the accumulator and
  53.  * x register in use-def computations.
  54.  * Currently, the use-def code assumes only one definition per instruction.
  55.  */
  56. #define AX_ATOM N_ATOMS
  57.  
  58. /*
  59.  * A flag to indicate that further optimization is needed.
  60.  * Iterative passes are continued until a given pass yields no
  61.  * branch movement.
  62.  */
  63. static int done;
  64.  
  65. /*
  66.  * A block is marked if only if its mark equals the current mark.
  67.  * Rather than traverse the code array, marking each item, 'cur_mark' is
  68.  * incremented.  This automatically makes each element unmarked.
  69.  */
  70. static int cur_mark;
  71. #define isMarked(p) ((p)->mark == cur_mark)
  72. #define unMarkAll() cur_mark += 1
  73. #define Mark(p) ((p)->mark = cur_mark)
  74.  
  75. static void opt_init(struct block *);
  76. static void opt_cleanup(void);
  77.  
  78. static void make_marks(struct block *);
  79. static void mark_code(struct block *);
  80.  
  81. static void intern_blocks(struct block *);
  82.  
  83. static int eq_slist(struct slist *, struct slist *);
  84.  
  85. static void find_levels_r(struct block *);
  86.  
  87. static void find_levels(struct block *);
  88. static void find_dom(struct block *);
  89. static void propedom(struct edge *);
  90. static void find_edom(struct block *);
  91. static void find_closure(struct block *);
  92. static int atomuse(struct stmt *);
  93. static int atomdef(struct stmt *);
  94. static void compute_local_ud(struct block *);
  95. static void find_ud(struct block *);
  96. static void init_val(void);
  97. static long F(int, long, long);
  98. static inline void vstore(struct stmt *, long *, long, int);
  99. static void opt_blk(struct block *, int);
  100. static int use_conflict(struct block *, struct block *);
  101. static void opt_j(struct edge *);
  102. static void or_pullup(struct block *);
  103. static void and_pullup(struct block *);
  104. static void opt_blks(struct block *, int);
  105. static inline void link_inedge(struct edge *, struct block *);
  106. static void find_inedges(struct block *);
  107. static void opt_root(struct block **);
  108. static void opt_loop(struct block *, int);
  109. static void fold_op(struct stmt *, long, long);
  110. static inline struct slist *this_op(struct slist *);
  111. static void opt_not(struct block *);
  112. static void opt_peep(struct block *);
  113. static void opt_stmt(struct stmt *, long[], int);
  114. static void deadstmt(struct stmt *, struct stmt *[]);
  115. static void opt_deadstores(struct block *);
  116. static void opt_blk(struct block *, int);
  117. static int use_conflict(struct block *, struct block *);
  118. static void opt_j(struct edge *);
  119. static struct block *fold_edge(struct block *, struct edge *);
  120. static inline int eq_blk(struct block *, struct block *);
  121. static int slength(struct slist *);
  122. static int count_blocks(struct block *);
  123. static void number_blks_r(struct block *);
  124. static int count_stmts(struct block *);
  125. static void convert_code_r(struct block *);
  126.  
  127. static int n_blocks;
  128. struct block **blocks;
  129. static int n_edges;
  130. struct edge **edges;
  131.  
  132. /*
  133.  * A bit vector set representation of the dominators.
  134.  * We round up the set size to the next power of two.
  135.  */
  136. static int nodewords;
  137. static int edgewords;
  138. struct block **levels;
  139. u_long *space;
  140. #define BITS_PER_WORD (8*sizeof(u_long))
  141. /*
  142.  * True if a is in uset {p}
  143.  */
  144. #define SET_MEMBER(p, a) \
  145. ((p)[(unsigned)(a) / BITS_PER_WORD] & (1 << ((unsigned)(a) % BITS_PER_WORD)))
  146.  
  147. /*
  148.  * Add 'a' to uset p.
  149.  */
  150. #define SET_INSERT(p, a) \
  151. (p)[(unsigned)(a) / BITS_PER_WORD] |= (1 << ((unsigned)(a) % BITS_PER_WORD))
  152.  
  153. /*
  154.  * Delete 'a' from uset p.
  155.  */
  156. #define SET_DELETE(p, a) \
  157. (p)[(unsigned)(a) / BITS_PER_WORD] &= ~(1 << ((unsigned)(a) % BITS_PER_WORD))
  158.  
  159. /*
  160.  * a := a intersect b
  161.  */
  162. #define SET_INTERSECT(a, b, n)\
  163. {\
  164.     register u_long *_x = a, *_y = b;\
  165.     register int _n = n;\
  166.     while (--_n >= 0) *_x++ &= *_y++;\
  167. }
  168.  
  169. /*
  170.  * a := a - b
  171.  */
  172. #define SET_SUBTRACT(a, b, n)\
  173. {\
  174.     register u_long *_x = a, *_y = b;\
  175.     register int _n = n;\
  176.     while (--_n >= 0) *_x++ &=~ *_y++;\
  177. }
  178.  
  179. /*
  180.  * a := a union b
  181.  */
  182. #define SET_UNION(a, b, n)\
  183. {\
  184.     register u_long *_x = a, *_y = b;\
  185.     register int _n = n;\
  186.     while (--_n >= 0) *_x++ |= *_y++;\
  187. }
  188.  
  189. static uset all_dom_sets;
  190. static uset all_closure_sets;
  191. static uset all_edge_sets;
  192.  
  193. #ifndef MAX
  194. #define MAX(a,b) ((a)>(b)?(a):(b))
  195. #endif
  196.  
  197. static void
  198. find_levels_r(b)
  199.     struct block *b;
  200. {
  201.     int level;
  202.  
  203.     if (isMarked(b))
  204.         return;
  205.  
  206.     Mark(b);
  207.     b->link = 0;
  208.  
  209.     if (JT(b)) {
  210.         find_levels_r(JT(b));
  211.         find_levels_r(JF(b));
  212.         level = MAX(JT(b)->level, JF(b)->level) + 1;
  213.     } else
  214.         level = 0;
  215.     b->level = level;
  216.     b->link = levels[level];
  217.     levels[level] = b;
  218. }
  219.  
  220. /*
  221.  * Level graph.  The levels go from 0 at the leaves to
  222.  * N_LEVELS at the root.  The levels[] array points to the
  223.  * first node of the level list, whose elements are linked
  224.  * with the 'link' field of the struct block.
  225.  */
  226. static void
  227. find_levels(root)
  228.     struct block *root;
  229. {
  230.     memset((char *)levels, 0, n_blocks * sizeof(*levels));
  231.     unMarkAll();
  232.     find_levels_r(root);
  233. }
  234.  
  235. /*
  236.  * Find dominator relationships.
  237.  * Assumes graph has been leveled.
  238.  */
  239. static void
  240. find_dom(root)
  241.     struct block *root;
  242. {
  243.     int i;
  244.     struct block *b;
  245.     u_long *x;
  246.  
  247.     /*
  248.      * Initialize sets to contain all nodes.
  249.      */
  250.     x = all_dom_sets;
  251.     i = n_blocks * nodewords;
  252.     while (--i >= 0)
  253.         *x++ = ~0;
  254.     /* Root starts off empty. */
  255.     for (i = nodewords; --i >= 0;)
  256.         root->dom[i] = 0;
  257.  
  258.     /* root->level is the highest level no found. */
  259.     for (i = root->level; i >= 0; --i) {
  260.         for (b = levels[i]; b; b = b->link) {
  261.             SET_INSERT(b->dom, b->id);
  262.             if (JT(b) == 0)
  263.                 continue;
  264.             SET_INTERSECT(JT(b)->dom, b->dom, nodewords);
  265.             SET_INTERSECT(JF(b)->dom, b->dom, nodewords);
  266.         }
  267.     }
  268. }
  269.  
  270. static void
  271. propedom(ep)
  272.     struct edge *ep;
  273. {
  274.     SET_INSERT(ep->edom, ep->id);
  275.     if (ep->succ) {
  276.         SET_INTERSECT(ep->succ->et.edom, ep->edom, edgewords);
  277.         SET_INTERSECT(ep->succ->ef.edom, ep->edom, edgewords);
  278.     }
  279. }
  280.  
  281. /*
  282.  * Compute edge dominators.
  283.  * Assumes graph has been leveled and predecessors established.
  284.  */
  285. static void
  286. find_edom(root)
  287.     struct block *root;
  288. {
  289.     int i;
  290.     uset x;
  291.     struct block *b;
  292.  
  293.     x = all_edge_sets;
  294.     for (i = n_edges * edgewords; --i >= 0; )
  295.         x[i] = ~0;
  296.  
  297.     /* root->level is the highest level no found. */
  298.     memset(root->et.edom, 0, edgewords * sizeof(*(uset)0));
  299.     memset(root->ef.edom, 0, edgewords * sizeof(*(uset)0));
  300.     for (i = root->level; i >= 0; --i) {
  301.         for (b = levels[i]; b != 0; b = b->link) {
  302.             propedom(&b->et);
  303.             propedom(&b->ef);
  304.         }
  305.     }
  306. }
  307.  
  308. /*
  309.  * Find the backwards transitive closure of the flow graph.  These sets
  310.  * are backwards in the sense that we find the set of nodes that reach
  311.  * a given node, not the set of nodes that can be reached by a node.
  312.  *
  313.  * Assumes graph has been leveled.
  314.  */
  315. static void
  316. find_closure(root)
  317.     struct block *root;
  318. {
  319.     int i;
  320.     struct block *b;
  321.  
  322.     /*
  323.      * Initialize sets to contain no nodes.
  324.      */
  325.     memset((char *)all_closure_sets, 0,
  326.           n_blocks * nodewords * sizeof(*all_closure_sets));
  327.  
  328.     /* root->level is the highest level no found. */
  329.     for (i = root->level; i >= 0; --i) {
  330.         for (b = levels[i]; b; b = b->link) {
  331.             SET_INSERT(b->closure, b->id);
  332.             if (JT(b) == 0)
  333.                 continue;
  334.             SET_UNION(JT(b)->closure, b->closure, nodewords);
  335.             SET_UNION(JF(b)->closure, b->closure, nodewords);
  336.         }
  337.     }
  338. }
  339.  
  340. /*
  341.  * Return the register number that is used by s.  If A and X are both
  342.  * used, return AX_ATOM.  If no register is used, return -1.
  343.  *
  344.  * The implementation should probably change to an array access.
  345.  */
  346. static int
  347. atomuse(s)
  348.     struct stmt *s;
  349. {
  350.     register int c = s->code;
  351.  
  352.     if (c == NOP)
  353.         return -1;
  354.  
  355.     switch (BPF_CLASS(c)) {
  356.  
  357.     case BPF_RET:
  358.         return (BPF_RVAL(c) == BPF_A) ? A_ATOM :
  359.             (BPF_RVAL(c) == BPF_X) ? X_ATOM : -1;
  360.  
  361.     case BPF_LD:
  362.     case BPF_LDX:
  363.         return (BPF_MODE(c) == BPF_IND) ? X_ATOM :
  364.             (BPF_MODE(c) == BPF_MEM) ? s->k : -1;
  365.  
  366.     case BPF_ST:
  367.         return A_ATOM;
  368.  
  369.     case BPF_STX:
  370.         return X_ATOM;
  371.  
  372.     case BPF_JMP:
  373.     case BPF_ALU:
  374.         if (BPF_SRC(c) == BPF_X)
  375.             return AX_ATOM;
  376.         return A_ATOM;
  377.  
  378.     case BPF_MISC:
  379.         return BPF_MISCOP(c) == BPF_TXA ? X_ATOM : A_ATOM;
  380.     }
  381.     abort();
  382.     /* NOTREACHED */
  383. }
  384.  
  385. /*
  386.  * Return the register number that is defined by 's'.  We assume that
  387.  * a single stmt cannot define more than one register.  If no register
  388.  * is defined, return -1.
  389.  *
  390.  * The implementation should probably change to an array access.
  391.  */
  392. static int
  393. atomdef(s)
  394.     struct stmt *s;
  395. {
  396.     if (s->code == NOP)
  397.         return -1;
  398.  
  399.     switch (BPF_CLASS(s->code)) {
  400.  
  401.     case BPF_LD:
  402.     case BPF_ALU:
  403.         return A_ATOM;
  404.  
  405.     case BPF_LDX:
  406.         return X_ATOM;
  407.  
  408.     case BPF_ST:
  409.     case BPF_STX:
  410.         return s->k;
  411.  
  412.     case BPF_MISC:
  413.         return BPF_MISCOP(s->code) == BPF_TAX ? X_ATOM : A_ATOM;
  414.     }
  415.     return -1;
  416. }
  417.  
  418. static void
  419. compute_local_ud(b)
  420.     struct block *b;
  421. {
  422.     struct slist *s;
  423.     atomset def = 0, use = 0, kill = 0;
  424.     int atom;
  425.  
  426.     for (s = b->stmts; s; s = s->next) {
  427.         if (s->s.code == NOP)
  428.             continue;
  429.         atom = atomuse(&s->s);
  430.         if (atom >= 0) {
  431.             if (atom == AX_ATOM) {
  432.                 if (!ATOMELEM(def, X_ATOM))
  433.                     use |= ATOMMASK(X_ATOM);
  434.                 if (!ATOMELEM(def, A_ATOM))
  435.                     use |= ATOMMASK(A_ATOM);
  436.             }
  437.             else if (atom < N_ATOMS) {
  438.                 if (!ATOMELEM(def, atom))
  439.                     use |= ATOMMASK(atom);
  440.             }
  441.             else
  442.                 abort();
  443.         }
  444.         atom = atomdef(&s->s);
  445.         if (atom >= 0) {
  446.             if (!ATOMELEM(use, atom))
  447.                 kill |= ATOMMASK(atom);
  448.             def |= ATOMMASK(atom);
  449.         }
  450.     }
  451.     if (!ATOMELEM(def, A_ATOM) && BPF_CLASS(b->s.code) == BPF_JMP)
  452.         use |= ATOMMASK(A_ATOM);
  453.  
  454.     b->def = def;
  455.     b->kill = kill;
  456.     b->in_use = use;
  457. }
  458.  
  459. /*
  460.  * Assume graph is already leveled.
  461.  */
  462. static void
  463. find_ud(root)
  464.     struct block *root;
  465. {
  466.     int i, maxlevel;
  467.     struct block *p;
  468.  
  469.     /*
  470.      * root->level is the highest level no found;
  471.      * count down from there.
  472.      */
  473.     maxlevel = root->level;
  474.     for (i = maxlevel; i >= 0; --i)
  475.         for (p = levels[i]; p; p = p->link) {
  476.             compute_local_ud(p);
  477.             p->out_use = 0;
  478.         }
  479.  
  480.     for (i = 1; i <= maxlevel; ++i) {
  481.         for (p = levels[i]; p; p = p->link) {
  482.             p->out_use |= JT(p)->in_use | JF(p)->in_use;
  483.             p->in_use |= p->out_use &~ p->kill;
  484.         }
  485.     }
  486. }
  487.  
  488. /*
  489.  * These data structures are used in a Cocke and Shwarz style
  490.  * value numbering scheme.  Since the flowgraph is acyclic,
  491.  * exit values can be propagated from a node's predecessors
  492.  * provided it is uniquely defined.
  493.  */
  494. struct valnode {
  495.     int code;
  496.     long v0, v1;
  497.     long val;
  498.     struct valnode *next;
  499. };
  500.  
  501. #define MODULUS 213
  502. static struct valnode *hashtbl[MODULUS];
  503. static int curval;
  504. static int maxval;
  505.  
  506. /* Integer constants mapped with the load immediate opcode. */
  507. #define K(i) F(BPF_LD|BPF_IMM|BPF_W, i, 0L)
  508.  
  509. struct vmapinfo {
  510.     int is_const;
  511.     long const_val;
  512. };
  513.  
  514. struct vmapinfo *vmap;
  515. struct valnode *vnode_base;
  516. struct valnode *next_vnode;
  517.  
  518. static void
  519. init_val()
  520. {
  521.     curval = 0;
  522.     next_vnode = vnode_base;
  523.     memset((char *)vmap, 0, maxval * sizeof(*vmap));
  524.     memset((char *)hashtbl, 0, sizeof hashtbl);
  525. }
  526.  
  527. /* Because we really don't have an IR, this stuff is a little messy. */
  528. static long
  529. F(code, v0, v1)
  530.     int code;
  531.     long v0, v1;
  532. {
  533.     u_int hash;
  534.     int val;
  535.     struct valnode *p;
  536.  
  537.     hash = (u_int)code ^ (v0 << 4) ^ (v1 << 8);
  538.     hash %= MODULUS;
  539.  
  540.     for (p = hashtbl[hash]; p; p = p->next)
  541.         if (p->code == code && p->v0 == v0 && p->v1 == v1)
  542.             return p->val;
  543.  
  544.     val = ++curval;
  545.     if (BPF_MODE(code) == BPF_IMM &&
  546.         (BPF_CLASS(code) == BPF_LD || BPF_CLASS(code) == BPF_LDX)) {
  547.         vmap[val].const_val = v0;
  548.         vmap[val].is_const = 1;
  549.     }
  550.     p = next_vnode++;
  551.     p->val = val;
  552.     p->code = code;
  553.     p->v0 = v0;
  554.     p->v1 = v1;
  555.     p->next = hashtbl[hash];
  556.     hashtbl[hash] = p;
  557.  
  558.     return val;
  559. }
  560.  
  561. static inline void
  562. vstore(s, valp, newval, alter)
  563.     struct stmt *s;
  564.     long *valp;
  565.     long newval;
  566.     int alter;
  567. {
  568.     if (alter && *valp == newval)
  569.         s->code = NOP;
  570.     else
  571.         *valp = newval;
  572. }
  573.  
  574. static void
  575. fold_op(s, v0, v1)
  576.     struct stmt *s;
  577.     long v0, v1;
  578. {
  579.     long a, b;
  580.  
  581.     a = vmap[v0].const_val;
  582.     b = vmap[v1].const_val;
  583.  
  584.     switch (BPF_OP(s->code)) {
  585.     case BPF_ADD:
  586.         a += b;
  587.         break;
  588.  
  589.     case BPF_SUB:
  590.         a -= b;
  591.         break;
  592.  
  593.     case BPF_MUL:
  594.         a *= b;
  595.         break;
  596.  
  597.     case BPF_DIV:
  598.         if (b == 0)
  599.             bpf_error("division by zero");
  600.         a /= b;
  601.         break;
  602.  
  603.     case BPF_AND:
  604.         a &= b;
  605.         break;
  606.  
  607.     case BPF_OR:
  608.         a |= b;
  609.         break;
  610.  
  611.     case BPF_LSH:
  612.         a <<= b;
  613.         break;
  614.  
  615.     case BPF_RSH:
  616.         a >>= b;
  617.         break;
  618.  
  619.     case BPF_NEG:
  620.         a = -a;
  621.         break;
  622.  
  623.     default:
  624.         abort();
  625.     }
  626.     s->k = a;
  627.     s->code = BPF_LD|BPF_IMM;
  628.     done = 0;
  629. }
  630.  
  631. static inline struct slist *
  632. this_op(s)
  633.     struct slist *s;
  634. {
  635.     while (s != 0 && s->s.code == NOP)
  636.         s = s->next;
  637.     return s;
  638. }
  639.  
  640. static void
  641. opt_not(b)
  642.     struct block *b;
  643. {
  644.     struct block *tmp = JT(b);
  645.  
  646.     JT(b) = JF(b);
  647.     JF(b) = tmp;
  648. }
  649.  
  650. static void
  651. opt_peep(b)
  652.     struct block *b;
  653. {
  654.     struct slist *s;
  655.     struct slist *next, *last;
  656.     int val;
  657.     long v;
  658.  
  659.     s = b->stmts;
  660.     if (s == 0)
  661.         return;
  662.  
  663.     last = s;
  664.     while (1) {
  665.         s = this_op(s);
  666.         if (s == 0)
  667.             break;
  668.         next = this_op(s->next);
  669.         if (next == 0)
  670.             break;
  671.         last = next;
  672.  
  673.         /*
  674.          * st  M[k]    -->    st  M[k]
  675.          * ldx M[k]        tax
  676.          */
  677.         if (s->s.code == BPF_ST &&
  678.             next->s.code == (BPF_LDX|BPF_MEM) &&
  679.             s->s.k == next->s.k) {
  680.             done = 0;
  681.             next->s.code = BPF_MISC|BPF_TAX;
  682.         }
  683.         /*
  684.          * ld  #k    -->    ldx  #k
  685.          * tax            txa
  686.          */
  687.         if (s->s.code == (BPF_LD|BPF_IMM) &&
  688.             next->s.code == (BPF_MISC|BPF_TAX)) {
  689.             s->s.code = BPF_LDX|BPF_IMM;
  690.             next->s.code = BPF_MISC|BPF_TXA;
  691.             done = 0;
  692.         }
  693.         /*
  694.          * This is an ugly special case, but it happens
  695.          * when you say tcp[k] or udp[k] where k is a constant.
  696.          */
  697.         if (s->s.code == (BPF_LD|BPF_IMM)) {
  698.             struct slist *add, *tax, *ild;
  699.  
  700.             /*
  701.              * Check that X isn't used on exit from this
  702.              * block (which the optimizer might cause).
  703.              * We know the code generator won't generate
  704.              * any local dependencies.
  705.              */
  706.             if (ATOMELEM(b->out_use, X_ATOM))
  707.                 break;
  708.  
  709.             if (next->s.code != (BPF_LDX|BPF_MSH|BPF_B))
  710.                 add = next;
  711.             else
  712.                 add = this_op(next->next);
  713.             if (add == 0 || add->s.code != (BPF_ALU|BPF_ADD|BPF_X))
  714.                 break;
  715.  
  716.             tax = this_op(add->next);
  717.             if (tax == 0 || tax->s.code != (BPF_MISC|BPF_TAX))
  718.                 break;
  719.  
  720.             ild = this_op(tax->next);
  721.             if (ild == 0 || BPF_CLASS(ild->s.code) != BPF_LD ||
  722.                 BPF_MODE(ild->s.code) != BPF_IND)
  723.                 break;
  724.             /*
  725.              * XXX We need to check that X is not
  726.              * subsequently used.  We know we can eliminate the
  727.              * accumulator modifications since it is defined
  728.              * by the last stmt of this sequence.
  729.              *
  730.              * We want to turn this sequence:
  731.              *
  732.              * (004) ldi     #0x2        {s}
  733.              * (005) ldxms   [14]        {next}  -- optional
  734.              * (006) addx            {add}
  735.              * (007) tax            {tax}
  736.              * (008) ild     [x+0]        {ild}
  737.              *
  738.              * into this sequence:
  739.              *
  740.              * (004) nop
  741.              * (005) ldxms   [14]
  742.              * (006) nop
  743.              * (007) nop
  744.              * (008) ild     [x+2]
  745.              *
  746.              */
  747.             ild->s.k += s->s.k;
  748.             s->s.code = NOP;
  749.             add->s.code = NOP;
  750.             tax->s.code = NOP;
  751.             done = 0;
  752.         }
  753.         s = next;
  754.     }
  755.     /*
  756.      * If we have a subtract to do a comparison, and the X register
  757.      * is a known constant, we can merge this value into the
  758.      * comparison.
  759.      */
  760.     if (last->s.code == (BPF_ALU|BPF_SUB|BPF_X) &&
  761.         !ATOMELEM(b->out_use, A_ATOM)) {
  762.         val = b->val[X_ATOM];
  763.         if (vmap[val].is_const) {
  764.             b->s.k += vmap[val].const_val;
  765.             last->s.code = NOP;
  766.             done = 0;
  767.         } else if (b->s.k == 0) {
  768.             /*
  769.              * sub x  ->    nop
  770.              * j  #0    j  x
  771.              */
  772.             last->s.code = NOP;
  773.             b->s.code = BPF_CLASS(b->s.code) | BPF_OP(b->s.code) |
  774.                 BPF_X;
  775.             done = 0;
  776.         }
  777.     }
  778.     /*
  779.      * Likewise, a constant subtract can be simplified.
  780.      */
  781.     else if (last->s.code == (BPF_ALU|BPF_SUB|BPF_K) &&
  782.          !ATOMELEM(b->out_use, A_ATOM)) {
  783.         b->s.k += last->s.k;
  784.         last->s.code = NOP;
  785.         done = 0;
  786.     }
  787.     /*
  788.      * and #k    nop
  789.      * jeq #0  ->    jset #k
  790.      */
  791.     if (last->s.code == (BPF_ALU|BPF_AND|BPF_K) &&
  792.         !ATOMELEM(b->out_use, A_ATOM) && b->s.k == 0) {
  793.         b->s.k = last->s.k;
  794.         b->s.code = BPF_JMP|BPF_K|BPF_JSET;
  795.         last->s.code = NOP;
  796.         done = 0;
  797.         opt_not(b);
  798.     }
  799.     /*
  800.      * If the accumulator is a known constant, we can compute the
  801.      * comparison result.
  802.      */
  803.     val = b->val[A_ATOM];
  804.     if (vmap[val].is_const && BPF_SRC(b->s.code) == BPF_K) {
  805.         v = vmap[val].const_val;
  806.         switch (BPF_OP(b->s.code)) {
  807.  
  808.         case BPF_JEQ:
  809.             v = v == b->s.k;
  810.             break;
  811.  
  812.         case BPF_JGT:
  813.             v = v > b->s.k;
  814.             break;
  815.  
  816.         case BPF_JGE:
  817.             v = v >= b->s.k;
  818.             break;
  819.  
  820.         case BPF_JSET:
  821.             v &= b->s.k;
  822.             break;
  823.  
  824.         default:
  825.             abort();
  826.         }
  827.         if (JF(b) != JT(b))
  828.             done = 0;
  829.         if (v)
  830.             JF(b) = JT(b);
  831.         else
  832.             JT(b) = JF(b);
  833.     }
  834. }
  835.  
  836. /*
  837.  * Compute the symbolic value of expression of 's', and update
  838.  * anything it defines in the value table 'val'.  If 'alter' is true,
  839.  * do various optimizations.  This code would be cleaner if symbolic
  840.  * evaluation and code transformations weren't folded together.
  841.  */
  842. static void
  843. opt_stmt(s, val, alter)
  844.     struct stmt *s;
  845.     long val[];
  846.     int alter;
  847. {
  848.     int op;
  849.     long v;
  850.  
  851.     switch (s->code) {
  852.  
  853.     case BPF_LD|BPF_ABS|BPF_W:
  854.     case BPF_LD|BPF_ABS|BPF_H:
  855.     case BPF_LD|BPF_ABS|BPF_B:
  856.         v = F(s->code, s->k, 0L);
  857.         vstore(s, &val[A_ATOM], v, alter);
  858.         break;
  859.  
  860.     case BPF_LD|BPF_IND|BPF_W:
  861.     case BPF_LD|BPF_IND|BPF_H:
  862.     case BPF_LD|BPF_IND|BPF_B:
  863.         v = val[X_ATOM];
  864.         if (alter && vmap[v].is_const) {
  865.             s->code = BPF_LD|BPF_ABS|BPF_SIZE(s->code);
  866.             s->k += vmap[v].const_val;
  867.             v = F(s->code, s->k, 0L);
  868.             done = 0;
  869.         }
  870.         else
  871.             v = F(s->code, s->k, v);
  872.         vstore(s, &val[A_ATOM], v, alter);
  873.         break;
  874.  
  875.     case BPF_LD|BPF_LEN:
  876.         v = F(s->code, 0L, 0L);
  877.         vstore(s, &val[A_ATOM], v, alter);
  878.         break;
  879.  
  880.     case BPF_LD|BPF_IMM:
  881.         v = K(s->k);
  882.         vstore(s, &val[A_ATOM], v, alter);
  883.         break;
  884.  
  885.     case BPF_LDX|BPF_IMM:
  886.         v = K(s->k);
  887.         vstore(s, &val[X_ATOM], v, alter);
  888.         break;
  889.  
  890.     case BPF_LDX|BPF_MSH|BPF_B:
  891.         v = F(s->code, s->k, 0L);
  892.         vstore(s, &val[X_ATOM], v, alter);
  893.         break;
  894.  
  895.     case BPF_ALU|BPF_NEG:
  896.         if (alter && vmap[val[A_ATOM]].is_const) {
  897.             s->code = BPF_LD|BPF_IMM;
  898.             s->k = -vmap[val[A_ATOM]].const_val;
  899.             val[A_ATOM] = K(s->k);
  900.         }
  901.         else
  902.             val[A_ATOM] = F(s->code, val[A_ATOM], 0L);
  903.         break;
  904.  
  905.     case BPF_ALU|BPF_ADD|BPF_K:
  906.     case BPF_ALU|BPF_SUB|BPF_K:
  907.     case BPF_ALU|BPF_MUL|BPF_K:
  908.     case BPF_ALU|BPF_DIV|BPF_K:
  909.     case BPF_ALU|BPF_AND|BPF_K:
  910.     case BPF_ALU|BPF_OR|BPF_K:
  911.     case BPF_ALU|BPF_LSH|BPF_K:
  912.     case BPF_ALU|BPF_RSH|BPF_K:
  913.         op = BPF_OP(s->code);
  914.         if (alter) {
  915.             if (s->k == 0) {
  916.                 if (op == BPF_ADD || op == BPF_SUB ||
  917.                     op == BPF_LSH || op == BPF_RSH ||
  918.                     op == BPF_OR) {
  919.                     s->code = NOP;
  920.                     break;
  921.                 }
  922.                 if (op == BPF_MUL || op == BPF_AND) {
  923.                     s->code = BPF_LD|BPF_IMM;
  924.                     val[A_ATOM] = K(s->k);
  925.                     break;
  926.                 }
  927.             }
  928.             if (vmap[val[A_ATOM]].is_const) {
  929.                 fold_op(s, val[A_ATOM], K(s->k));
  930.                 val[A_ATOM] = K(s->k);
  931.                 break;
  932.             }
  933.         }
  934.         val[A_ATOM] = F(s->code, val[A_ATOM], K(s->k));
  935.         break;
  936.  
  937.     case BPF_ALU|BPF_ADD|BPF_X:
  938.     case BPF_ALU|BPF_SUB|BPF_X:
  939.     case BPF_ALU|BPF_MUL|BPF_X:
  940.     case BPF_ALU|BPF_DIV|BPF_X:
  941.     case BPF_ALU|BPF_AND|BPF_X:
  942.     case BPF_ALU|BPF_OR|BPF_X:
  943.     case BPF_ALU|BPF_LSH|BPF_X:
  944.     case BPF_ALU|BPF_RSH|BPF_X:
  945.         op = BPF_OP(s->code);
  946.         if (alter && vmap[val[X_ATOM]].is_const) {
  947.             if (vmap[val[A_ATOM]].is_const) {
  948.                 fold_op(s, val[A_ATOM], val[X_ATOM]);
  949.                 val[A_ATOM] = K(s->k);
  950.             }
  951.             else {
  952.                 s->code = BPF_ALU|BPF_K|op;
  953.                 s->k = vmap[val[X_ATOM]].const_val;
  954.                 done = 0;
  955.                 val[A_ATOM] =
  956.                     F(s->code, val[A_ATOM], K(s->k));
  957.             }
  958.             break;
  959.         }
  960.         /*
  961.          * Check if we're doing something to an accumulator
  962.          * that is 0, and simplify.  This may not seem like
  963.          * much of a simplification but it could open up further
  964.          * optimizations.
  965.          * XXX We could also check for mul by 1, and -1, etc.
  966.          */
  967.         if (alter && vmap[val[A_ATOM]].is_const
  968.             && vmap[val[A_ATOM]].const_val == 0) {
  969.             if (op == BPF_ADD || op == BPF_OR ||
  970.                 op == BPF_LSH || op == BPF_RSH || op == BPF_SUB) {
  971.                 s->code = BPF_MISC|BPF_TXA;
  972.                 vstore(s, &val[A_ATOM], val[X_ATOM], alter);
  973.                 break;
  974.             }
  975.             else if (op == BPF_MUL || op == BPF_DIV ||
  976.                  op == BPF_AND) {
  977.                 s->code = BPF_LD|BPF_IMM;
  978.                 s->k = 0;
  979.                 vstore(s, &val[A_ATOM], K(s->k), alter);
  980.                 break;
  981.             }
  982.             else if (op == BPF_NEG) {
  983.                 s->code = NOP;
  984.                 break;
  985.             }
  986.         }
  987.         val[A_ATOM] = F(s->code, val[A_ATOM], val[X_ATOM]);
  988.         break;
  989.  
  990.     case BPF_MISC|BPF_TXA:
  991.         vstore(s, &val[A_ATOM], val[X_ATOM], alter);
  992.         break;
  993.  
  994.     case BPF_LD|BPF_MEM:
  995.         v = val[s->k];
  996.         if (alter && vmap[v].is_const) {
  997.             s->code = BPF_LD|BPF_IMM;
  998.             s->k = vmap[v].const_val;
  999.             done = 0;
  1000.         }
  1001.         vstore(s, &val[A_ATOM], v, alter);
  1002.         break;
  1003.  
  1004.     case BPF_MISC|BPF_TAX:
  1005.         vstore(s, &val[X_ATOM], val[A_ATOM], alter);
  1006.         break;
  1007.  
  1008.     case BPF_LDX|BPF_MEM:
  1009.         v = val[s->k];
  1010.         if (alter && vmap[v].is_const) {
  1011.             s->code = BPF_LDX|BPF_IMM;
  1012.             s->k = vmap[v].const_val;
  1013.             done = 0;
  1014.         }
  1015.         vstore(s, &val[X_ATOM], v, alter);
  1016.         break;
  1017.  
  1018.     case BPF_ST:
  1019.         vstore(s, &val[s->k], val[A_ATOM], alter);
  1020.         break;
  1021.  
  1022.     case BPF_STX:
  1023.         vstore(s, &val[s->k], val[X_ATOM], alter);
  1024.         break;
  1025.     }
  1026. }
  1027.  
  1028. static void
  1029. deadstmt(s, last)
  1030.     register struct stmt *s;
  1031.     register struct stmt *last[];
  1032. {
  1033.     register int atom;
  1034.  
  1035.     atom = atomuse(s);
  1036.     if (atom >= 0) {
  1037.         if (atom == AX_ATOM) {
  1038.             last[X_ATOM] = 0;
  1039.             last[A_ATOM] = 0;
  1040.         }
  1041.         else
  1042.             last[atom] = 0;
  1043.     }
  1044.     atom = atomdef(s);
  1045.     if (atom >= 0) {
  1046.         if (last[atom]) {
  1047.             done = 0;
  1048.             last[atom]->code = NOP;
  1049.         }
  1050.         last[atom] = s;
  1051.     }
  1052. }
  1053.  
  1054. static void
  1055. opt_deadstores(b)
  1056.     register struct block *b;
  1057. {
  1058.     register struct slist *s;
  1059.     register int atom;
  1060.     struct stmt *last[N_ATOMS];
  1061.  
  1062.     memset((char *)last, 0, sizeof last);
  1063.  
  1064.     for (s = b->stmts; s != 0; s = s->next)
  1065.         deadstmt(&s->s, last);
  1066.     deadstmt(&b->s, last);
  1067.  
  1068.     for (atom = 0; atom < N_ATOMS; ++atom)
  1069.         if (last[atom] && !ATOMELEM(b->out_use, atom)) {
  1070.             last[atom]->code = NOP;
  1071.             done = 0;
  1072.         }
  1073. }
  1074.  
  1075. static void
  1076. opt_blk(b, do_stmts)
  1077.     struct block *b;
  1078.     int do_stmts;
  1079. {
  1080.     struct slist *s;
  1081.     struct edge *p;
  1082.     int i;
  1083.     long aval;
  1084.  
  1085.     /*
  1086.      * Initialize the atom values.
  1087.      * If we have no predecessors, everything is undefined.
  1088.      * Otherwise, we inherent our values from our predecessors.
  1089.      * If any register has an ambiguous value (i.e. control paths are
  1090.      * merging) give it the undefined value of 0.
  1091.      */
  1092.     p = b->in_edges;
  1093.     if (p == 0)
  1094.         memset((char *)b->val, 0, sizeof(b->val));
  1095.     else {
  1096.         memcpy((char *)b->val, (char *)p->pred->val, sizeof(b->val));
  1097.         while ((p = p->next) != NULL) {
  1098.             for (i = 0; i < N_ATOMS; ++i)
  1099.                 if (b->val[i] != p->pred->val[i])
  1100.                     b->val[i] = 0;
  1101.         }
  1102.     }
  1103.     aval = b->val[A_ATOM];
  1104.     for (s = b->stmts; s; s = s->next)
  1105.         opt_stmt(&s->s, b->val, do_stmts);
  1106.  
  1107.     /*
  1108.      * This is a special case: if we don't use anything from this
  1109.      * block, and we load the accumulator with value that is
  1110.      * already there, eliminate all the statements.
  1111.      */
  1112.     if (do_stmts && b->out_use == 0 && aval != 0 &&
  1113.         b->val[A_ATOM] == aval)
  1114.         b->stmts = 0;
  1115.     else {
  1116.         opt_peep(b);
  1117.         opt_deadstores(b);
  1118.     }
  1119.     /*
  1120.      * Set up values for branch optimizer.
  1121.      */
  1122.     if (BPF_SRC(b->s.code) == BPF_K)
  1123.         b->oval = K(b->s.k);
  1124.     else
  1125.         b->oval = b->val[X_ATOM];
  1126.     b->et.code = b->s.code;
  1127.     b->ef.code = -b->s.code;
  1128. }
  1129.  
  1130. /*
  1131.  * Return true if any register that is used on exit from 'succ', has
  1132.  * an exit value that is different from the corresponding exit value
  1133.  * from 'b'.
  1134.  */
  1135. static int
  1136. use_conflict(b, succ)
  1137.     struct block *b, *succ;
  1138. {
  1139.     int atom;
  1140.     atomset use = succ->out_use;
  1141.  
  1142.     if (use == 0)
  1143.         return 0;
  1144.  
  1145.     for (atom = 0; atom < N_ATOMS; ++atom)
  1146.         if (ATOMELEM(use, atom))
  1147.             if (b->val[atom] != succ->val[atom])
  1148.                 return 1;
  1149.     return 0;
  1150. }
  1151.  
  1152. static struct block *
  1153. fold_edge(child, ep)
  1154.     struct block *child;
  1155.     struct edge *ep;
  1156. {
  1157.     int sense;
  1158.     int aval0, aval1, oval0, oval1;
  1159.     int code = ep->code;
  1160.  
  1161.     if (code < 0) {
  1162.         code = -code;
  1163.         sense = 0;
  1164.     } else
  1165.         sense = 1;
  1166.  
  1167.     if (child->s.code != code)
  1168.         return 0;
  1169.  
  1170.     aval0 = child->val[A_ATOM];
  1171.     oval0 = child->oval;
  1172.     aval1 = ep->pred->val[A_ATOM];
  1173.     oval1 = ep->pred->oval;
  1174.  
  1175.     if (aval0 != aval1)
  1176.         return 0;
  1177.  
  1178.     if (oval0 == oval1)
  1179.         /*
  1180.          * The operands are identical, so the
  1181.          * result is true if a true branch was
  1182.          * taken to get here, otherwise false.
  1183.          */
  1184.         return sense ? JT(child) : JF(child);
  1185.  
  1186.     if (sense && code == (BPF_JMP|BPF_JEQ|BPF_K))
  1187.         /*
  1188.          * At this point, we only know the comparison if we
  1189.          * came down the true branch, and it was an equality
  1190.          * comparison with a constant.  We rely on the fact that
  1191.          * distinct constants have distinct value numbers.
  1192.          */
  1193.         return JF(child);
  1194.  
  1195.     return 0;
  1196. }
  1197.  
  1198. static void
  1199. opt_j(ep)
  1200.     struct edge *ep;
  1201. {
  1202.     register int i, k;
  1203.     register struct block *target;
  1204.  
  1205.     if (JT(ep->succ) == 0)
  1206.         return;
  1207.  
  1208.     if (JT(ep->succ) == JF(ep->succ)) {
  1209.         /*
  1210.          * Common branch targets can be eliminated, provided
  1211.          * there is no data dependency.
  1212.          */
  1213.         if (!use_conflict(ep->pred, ep->succ->et.succ)) {
  1214.             done = 0;
  1215.             ep->succ = JT(ep->succ);
  1216.         }
  1217.     }
  1218.     /*
  1219.      * For each edge dominator that matches the successor of this
  1220.      * edge, promote the edge successor to the its grandchild.
  1221.      *
  1222.      * XXX We violate the set abstraction here in favor a reasonably
  1223.      * efficient loop.
  1224.      */
  1225.  top:
  1226.     for (i = 0; i < edgewords; ++i) {
  1227.         register u_long x = ep->edom[i];
  1228.  
  1229.         while (x != 0) {
  1230.             k = ffs(x) - 1;
  1231.             x &=~ (1 << k);
  1232.             k += i * BITS_PER_WORD;
  1233.  
  1234.             target = fold_edge(ep->succ, edges[k]);
  1235.             /*
  1236.              * Check that there is no data dependency between
  1237.              * nodes that will be violated if we move the edge.
  1238.              */
  1239.             if (target != 0 && !use_conflict(ep->pred, target)) {
  1240.                 done = 0;
  1241.                 ep->succ = target;
  1242.                 if (JT(target) != 0)
  1243.                     /*
  1244.                      * Start over unless we hit a leaf.
  1245.                      */
  1246.                     goto top;
  1247.                 return;
  1248.             }
  1249.         }
  1250.     }
  1251. }
  1252.  
  1253.  
  1254. static void
  1255. or_pullup(b)
  1256.     struct block *b;
  1257. {
  1258.     int val, at_top;
  1259.     struct block *pull;
  1260.     struct block **diffp, **samep;
  1261.     struct edge *ep;
  1262.  
  1263.     ep = b->in_edges;
  1264.     if (ep == 0)
  1265.         return;
  1266.  
  1267.     /*
  1268.      * Make sure each predecessor loads the same value.
  1269.      * XXX why?
  1270.      */
  1271.     val = ep->pred->val[A_ATOM];
  1272.     for (ep = ep->next; ep != 0; ep = ep->next)
  1273.         if (val != ep->pred->val[A_ATOM])
  1274.             return;
  1275.  
  1276.     if (JT(b->in_edges->pred) == b)
  1277.         diffp = &JT(b->in_edges->pred);
  1278.     else
  1279.         diffp = &JF(b->in_edges->pred);
  1280.  
  1281.     at_top = 1;
  1282.     while (1) {
  1283.         if (*diffp == 0)
  1284.             return;
  1285.  
  1286.         if (JT(*diffp) != JT(b))
  1287.             return;
  1288.  
  1289.         if (!SET_MEMBER((*diffp)->dom, b->id))
  1290.             return;
  1291.  
  1292.         if ((*diffp)->val[A_ATOM] != val)
  1293.             break;
  1294.  
  1295.         diffp = &JF(*diffp);
  1296.         at_top = 0;
  1297.     }
  1298.     samep = &JF(*diffp);
  1299.     while (1) {
  1300.         if (*samep == 0)
  1301.             return;
  1302.  
  1303.         if (JT(*samep) != JT(b))
  1304.             return;
  1305.  
  1306.         if (!SET_MEMBER((*samep)->dom, b->id))
  1307.             return;
  1308.  
  1309.         if ((*samep)->val[A_ATOM] == val)
  1310.             break;
  1311.  
  1312.         /* XXX Need to check that there are no data dependencies
  1313.            between dp0 and dp1.  Currently, the code generator
  1314.            will not produce such dependencies. */
  1315.         samep = &JF(*samep);
  1316.     }
  1317. #ifdef notdef
  1318.     /* XXX This doesn't cover everything. */
  1319.     for (i = 0; i < N_ATOMS; ++i)
  1320.         if ((*samep)->val[i] != pred->val[i])
  1321.             return;
  1322. #endif
  1323.     /* Pull up the node. */
  1324.     pull = *samep;
  1325.     *samep = JF(pull);
  1326.     JF(pull) = *diffp;
  1327.  
  1328.     /*
  1329.      * At the top of the chain, each predecessor needs to point at the
  1330.      * pulled up node.  Inside the chain, there is only one predecessor
  1331.      * to worry about.
  1332.      */
  1333.     if (at_top) {
  1334.         for (ep = b->in_edges; ep != 0; ep = ep->next) {
  1335.             if (JT(ep->pred) == b)
  1336.                 JT(ep->pred) = pull;
  1337.             else
  1338.                 JF(ep->pred) = pull;
  1339.         }
  1340.     }
  1341.     else
  1342.         *diffp = pull;
  1343.  
  1344.     done = 0;
  1345. }
  1346.  
  1347. static void
  1348. and_pullup(b)
  1349.     struct block *b;
  1350. {
  1351.     int val, at_top;
  1352.     struct block *pull;
  1353.     struct block **diffp, **samep;
  1354.     struct edge *ep;
  1355.  
  1356.     ep = b->in_edges;
  1357.     if (ep == 0)
  1358.         return;
  1359.  
  1360.     /*
  1361.      * Make sure each predecessor loads the same value.
  1362.      */
  1363.     val = ep->pred->val[A_ATOM];
  1364.     for (ep = ep->next; ep != 0; ep = ep->next)
  1365.         if (val != ep->pred->val[A_ATOM])
  1366.             return;
  1367.  
  1368.     if (JT(b->in_edges->pred) == b)
  1369.         diffp = &JT(b->in_edges->pred);
  1370.     else
  1371.         diffp = &JF(b->in_edges->pred);
  1372.  
  1373.     at_top = 1;
  1374.     while (1) {
  1375.         if (*diffp == 0)
  1376.             return;
  1377.  
  1378.         if (JF(*diffp) != JF(b))
  1379.             return;
  1380.  
  1381.         if (!SET_MEMBER((*diffp)->dom, b->id))
  1382.             return;
  1383.  
  1384.         if ((*diffp)->val[A_ATOM] != val)
  1385.             break;
  1386.  
  1387.         diffp = &JT(*diffp);
  1388.         at_top = 0;
  1389.     }
  1390.     samep = &JT(*diffp);
  1391.     while (1) {
  1392.         if (*samep == 0)
  1393.             return;
  1394.  
  1395.         if (JF(*samep) != JF(b))
  1396.             return;
  1397.  
  1398.         if (!SET_MEMBER((*samep)->dom, b->id))
  1399.             return;
  1400.  
  1401.         if ((*samep)->val[A_ATOM] == val)
  1402.             break;
  1403.  
  1404.         /* XXX Need to check that there are no data dependencies
  1405.            between diffp and samep.  Currently, the code generator
  1406.            will not produce such dependencies. */
  1407.         samep = &JT(*samep);
  1408.     }
  1409. #ifdef notdef
  1410.     /* XXX This doesn't cover everything. */
  1411.     for (i = 0; i < N_ATOMS; ++i)
  1412.         if ((*samep)->val[i] != pred->val[i])
  1413.             return;
  1414. #endif
  1415.     /* Pull up the node. */
  1416.     pull = *samep;
  1417.     *samep = JT(pull);
  1418.     JT(pull) = *diffp;
  1419.  
  1420.     /*
  1421.      * At the top of the chain, each predecessor needs to point at the
  1422.      * pulled up node.  Inside the chain, there is only one predecessor
  1423.      * to worry about.
  1424.      */
  1425.     if (at_top) {
  1426.         for (ep = b->in_edges; ep != 0; ep = ep->next) {
  1427.             if (JT(ep->pred) == b)
  1428.                 JT(ep->pred) = pull;
  1429.             else
  1430.                 JF(ep->pred) = pull;
  1431.         }
  1432.     }
  1433.     else
  1434.         *diffp = pull;
  1435.  
  1436.     done = 0;
  1437. }
  1438.  
  1439. static void
  1440. opt_blks(root, do_stmts)
  1441.     struct block *root;
  1442.     int do_stmts;
  1443. {
  1444.     int i, maxlevel;
  1445.     struct block *p;
  1446.  
  1447.     init_val();
  1448.     maxlevel = root->level;
  1449.     for (i = maxlevel; i >= 0; --i)
  1450.         for (p = levels[i]; p; p = p->link)
  1451.             opt_blk(p, do_stmts);
  1452.  
  1453.     if (do_stmts)
  1454.         /*
  1455.          * No point trying to move branches; it can't possibly
  1456.          * make a difference at this point.
  1457.          */
  1458.         return;
  1459.  
  1460.     for (i = 1; i <= maxlevel; ++i) {
  1461.         for (p = levels[i]; p; p = p->link) {
  1462.             opt_j(&p->et);
  1463.             opt_j(&p->ef);
  1464.         }
  1465.     }
  1466.     for (i = 1; i <= maxlevel; ++i) {
  1467.         for (p = levels[i]; p; p = p->link) {
  1468.             or_pullup(p);
  1469.             and_pullup(p);
  1470.         }
  1471.     }
  1472. }
  1473.  
  1474. static inline void
  1475. link_inedge(parent, child)
  1476.     struct edge *parent;
  1477.     struct block *child;
  1478. {
  1479.     parent->next = child->in_edges;
  1480.     child->in_edges = parent;
  1481. }
  1482.  
  1483. static void
  1484. find_inedges(root)
  1485.     struct block *root;
  1486. {
  1487.     int i;
  1488.     struct block *b;
  1489.  
  1490.     for (i = 0; i < n_blocks; ++i)
  1491.         blocks[i]->in_edges = 0;
  1492.  
  1493.     /*
  1494.      * Traverse the graph, adding each edge to the predecessor
  1495.      * list of its successors.  Skip the leaves (i.e. level 0).
  1496.      */
  1497.     for (i = root->level; i > 0; --i) {
  1498.         for (b = levels[i]; b != 0; b = b->link) {
  1499.             link_inedge(&b->et, JT(b));
  1500.             link_inedge(&b->ef, JF(b));
  1501.         }
  1502.     }
  1503. }
  1504.  
  1505. static void
  1506. opt_root(b)
  1507.     struct block **b;
  1508. {
  1509.     struct slist *tmp, *s;
  1510.  
  1511.     s = (*b)->stmts;
  1512.     (*b)->stmts = 0;
  1513.     while (BPF_CLASS((*b)->s.code) == BPF_JMP && JT(*b) == JF(*b))
  1514.         *b = JT(*b);
  1515.  
  1516.     tmp = (*b)->stmts;
  1517.     if (tmp != 0)
  1518.         sappend(s, tmp);
  1519.     (*b)->stmts = s;
  1520. }
  1521.  
  1522. static void
  1523. opt_loop(root, do_stmts)
  1524.     struct block *root;
  1525.     int do_stmts;
  1526. {
  1527.  
  1528. #ifdef BDEBUG
  1529.     if (dflag > 1)
  1530.         opt_dump(root);
  1531. #endif
  1532.     do {
  1533.         done = 1;
  1534.         find_levels(root);
  1535.         find_dom(root);
  1536.         find_closure(root);
  1537.         find_inedges(root);
  1538.         find_ud(root);
  1539.         find_edom(root);
  1540.         opt_blks(root, do_stmts);
  1541. #ifdef BDEBUG
  1542.         if (dflag > 1)
  1543.             opt_dump(root);
  1544. #endif
  1545.     } while (!done);
  1546. }
  1547.  
  1548. /*
  1549.  * Optimize the filter code in its dag representation.
  1550.  */
  1551. void
  1552. bpf_optimize(rootp)
  1553.     struct block **rootp;
  1554. {
  1555.     struct block *root;
  1556.  
  1557.     root = *rootp;
  1558.  
  1559.     opt_init(root);
  1560.     opt_loop(root, 0);
  1561.     opt_loop(root, 1);
  1562.     intern_blocks(root);
  1563.     opt_root(rootp);
  1564.     opt_cleanup();
  1565. }
  1566.  
  1567. static void
  1568. make_marks(p)
  1569.     struct block *p;
  1570. {
  1571.     if (!isMarked(p)) {
  1572.         Mark(p);
  1573.         if (BPF_CLASS(p->s.code) != BPF_RET) {
  1574.             make_marks(JT(p));
  1575.             make_marks(JF(p));
  1576.         }
  1577.     }
  1578. }
  1579.  
  1580. /*
  1581.  * Mark code array such that isMarked(i) is true
  1582.  * only for nodes that are alive.
  1583.  */
  1584. static void
  1585. mark_code(p)
  1586.     struct block *p;
  1587. {
  1588.     cur_mark += 1;
  1589.     make_marks(p);
  1590. }
  1591.  
  1592. /*
  1593.  * True iff the two stmt lists load the same value from the packet into
  1594.  * the accumulator.
  1595.  */
  1596. static int
  1597. eq_slist(x, y)
  1598.     struct slist *x, *y;
  1599. {
  1600.     while (1) {
  1601.         while (x && x->s.code == NOP)
  1602.             x = x->next;
  1603.         while (y && y->s.code == NOP)
  1604.             y = y->next;
  1605.         if (x == 0)
  1606.             return y == 0;
  1607.         if (y == 0)
  1608.             return x == 0;
  1609.         if (x->s.code != y->s.code || x->s.k != y->s.k)
  1610.             return 0;
  1611.         x = x->next;
  1612.         y = y->next;
  1613.     }
  1614. }
  1615.  
  1616. static inline int
  1617. eq_blk(b0, b1)
  1618.     struct block *b0, *b1;
  1619. {
  1620.     if (b0->s.code == b1->s.code &&
  1621.         b0->s.k == b1->s.k &&
  1622.         b0->et.succ == b1->et.succ &&
  1623.         b0->ef.succ == b1->ef.succ)
  1624.         return eq_slist(b0->stmts, b1->stmts);
  1625.     return 0;
  1626. }
  1627.  
  1628. static void
  1629. intern_blocks(root)
  1630.     struct block *root;
  1631. {
  1632.     struct block *p;
  1633.     int i, j;
  1634.     int done;
  1635.  top:
  1636.     done = 1;
  1637.     for (i = 0; i < n_blocks; ++i)
  1638.         blocks[i]->link = 0;
  1639.  
  1640.     mark_code(root);
  1641.  
  1642.     for (i = n_blocks - 1; --i >= 0; ) {
  1643.         if (!isMarked(blocks[i]))
  1644.             continue;
  1645.         for (j = i + 1; j < n_blocks; ++j) {
  1646.             if (!isMarked(blocks[j]))
  1647.                 continue;
  1648.             if (eq_blk(blocks[i], blocks[j])) {
  1649.                 blocks[i]->link = blocks[j]->link ?
  1650.                     blocks[j]->link : blocks[j];
  1651.                 break;
  1652.             }
  1653.         }
  1654.     }
  1655.     for (i = 0; i < n_blocks; ++i) {
  1656.         p = blocks[i];
  1657.         if (JT(p) == 0)
  1658.             continue;
  1659.         if (JT(p)->link) {
  1660.             done = 0;
  1661.             JT(p) = JT(p)->link;
  1662.         }
  1663.         if (JF(p)->link) {
  1664.             done = 0;
  1665.             JF(p) = JF(p)->link;
  1666.         }
  1667.     }
  1668.     if (!done)
  1669.         goto top;
  1670. }
  1671.  
  1672. static void
  1673. opt_cleanup()
  1674. {
  1675.     free((void *)vnode_base);
  1676.     free((void *)vmap);
  1677.     free((void *)edges);
  1678.     free((void *)space);
  1679.     free((void *)levels);
  1680.     free((void *)blocks);
  1681. }
  1682.  
  1683. /*
  1684.  * Return the number of stmts in 's'.
  1685.  */
  1686. static int
  1687. slength(s)
  1688.     struct slist *s;
  1689. {
  1690.     int n = 0;
  1691.  
  1692.     for (; s; s = s->next)
  1693.         if (s->s.code != NOP)
  1694.             ++n;
  1695.     return n;
  1696. }
  1697.  
  1698. /*
  1699.  * Return the number of nodes reachable by 'p'.
  1700.  * All nodes should be initially unmarked.
  1701.  */
  1702. static int
  1703. count_blocks(p)
  1704.     struct block *p;
  1705. {
  1706.     if (p == 0 || isMarked(p))
  1707.         return 0;
  1708.     Mark(p);
  1709.     return count_blocks(JT(p)) + count_blocks(JF(p)) + 1;
  1710. }
  1711.  
  1712. /*
  1713.  * Do a depth first search on the flow graph, numbering the
  1714.  * the basic blocks, and entering them into the 'blocks' array.`
  1715.  */
  1716. static void
  1717. number_blks_r(p)
  1718.     struct block *p;
  1719. {
  1720.     int n;
  1721.  
  1722.     if (p == 0 || isMarked(p))
  1723.         return;
  1724.  
  1725.     Mark(p);
  1726.     n = n_blocks++;
  1727.     p->id = n;
  1728.     blocks[n] = p;
  1729.  
  1730.     number_blks_r(JT(p));
  1731.     number_blks_r(JF(p));
  1732. }
  1733.  
  1734. /*
  1735.  * Return the number of stmts in the flowgraph reachable by 'p'.
  1736.  * The nodes should be unmarked before calling.
  1737.  */
  1738. static int
  1739. count_stmts(p)
  1740.     struct block *p;
  1741. {
  1742.     int n;
  1743.  
  1744.     if (p == 0 || isMarked(p))
  1745.         return 0;
  1746.     Mark(p);
  1747.     n = count_stmts(JT(p)) + count_stmts(JF(p));
  1748.     return slength(p->stmts) + n + 1;
  1749. }
  1750.  
  1751. /*
  1752.  * Allocate memory.  All allocation is done before optimization
  1753.  * is begun.  A linear bound on the size of all data structures is computed
  1754.  * from the total number of blocks and/or statements.
  1755.  */
  1756. static void
  1757. opt_init(root)
  1758.     struct block *root;
  1759. {
  1760.     u_long *p;
  1761.     int i, n, max_stmts;
  1762.  
  1763.     /*
  1764.      * First, count the blocks, so we can malloc an array to map
  1765.      * block number to block.  Then, put the blocks into the array.
  1766.      */
  1767.     unMarkAll();
  1768.     n = count_blocks(root);
  1769.     blocks = (struct block **)malloc(n * sizeof(*blocks));
  1770.     unMarkAll();
  1771.     n_blocks = 0;
  1772.     number_blks_r(root);
  1773.  
  1774.     n_edges = 2 * n_blocks;
  1775.     edges = (struct edge **)malloc(n_edges * sizeof(*edges));
  1776.  
  1777.     /*
  1778.      * The number of levels is bounded by the number of nodes.
  1779.      */
  1780.     levels = (struct block **)malloc(n_blocks * sizeof(*levels));
  1781.  
  1782.     edgewords = n_edges / (8 * sizeof(u_long)) + 1;
  1783.     nodewords = n_blocks / (8 * sizeof(u_long)) + 1;
  1784.  
  1785.     /* XXX */
  1786.     space = (u_long *)malloc(2 * n_blocks * nodewords * sizeof(*space)
  1787.                  + n_edges * edgewords * sizeof(*space));
  1788.     p = space;
  1789.     all_dom_sets = p;
  1790.     for (i = 0; i < n; ++i) {
  1791.         blocks[i]->dom = p;
  1792.         p += nodewords;
  1793.     }
  1794.     all_closure_sets = p;
  1795.     for (i = 0; i < n; ++i) {
  1796.         blocks[i]->closure = p;
  1797.         p += nodewords;
  1798.     }
  1799.     all_edge_sets = p;
  1800.     for (i = 0; i < n; ++i) {
  1801.         register struct block *b = blocks[i];
  1802.  
  1803.         b->et.edom = p;
  1804.         p += edgewords;
  1805.         b->ef.edom = p;
  1806.         p += edgewords;
  1807.         b->et.id = i;
  1808.         edges[i] = &b->et;
  1809.         b->ef.id = n_blocks + i;
  1810.         edges[n_blocks + i] = &b->ef;
  1811.         b->et.pred = b;
  1812.         b->ef.pred = b;
  1813.     }
  1814.     max_stmts = 0;
  1815.     for (i = 0; i < n; ++i)
  1816.         max_stmts += slength(blocks[i]->stmts) + 1;
  1817.     /*
  1818.      * We allocate at most 3 value numbers per statement,
  1819.      * so this is an upper bound on the number of valnodes
  1820.      * we'll need.
  1821.      */
  1822.     maxval = 3 * max_stmts;
  1823.     vmap = (struct vmapinfo *)malloc(maxval * sizeof(*vmap));
  1824.     vnode_base = (struct valnode *)malloc(maxval * sizeof(*vmap));
  1825. }
  1826.  
  1827. /*
  1828.  * Some pointers used to convert the basic block form of the code,
  1829.  * into the array form that BPF requires.  'fstart' will point to
  1830.  * the malloc'd array while 'ftail' is used during the recursive traversal.
  1831.  */
  1832. static struct bpf_insn *fstart;
  1833. static struct bpf_insn *ftail;
  1834.  
  1835. #ifdef BDEBUG
  1836. int bids[1000];
  1837. #endif
  1838.  
  1839. static void
  1840. convert_code_r(p)
  1841.     struct block *p;
  1842. {
  1843.     struct bpf_insn *dst;
  1844.     struct slist *src;
  1845.     int slen;
  1846.     u_int off;
  1847.  
  1848.     if (p == 0 || isMarked(p))
  1849.         return;
  1850.     Mark(p);
  1851.  
  1852.     convert_code_r(JF(p));
  1853.     convert_code_r(JT(p));
  1854.  
  1855.     slen = slength(p->stmts);
  1856.     dst = ftail -= slen + 1;
  1857.  
  1858.     p->offset = dst - fstart;
  1859.  
  1860.     for (src = p->stmts; src; src = src->next) {
  1861.         if (src->s.code == NOP)
  1862.             continue;
  1863.         dst->code = (u_short)src->s.code;
  1864.         dst->k = src->s.k;
  1865.         ++dst;
  1866.     }
  1867. #ifdef BDEBUG
  1868.     bids[dst - fstart] = p->id + 1;
  1869. #endif
  1870.     dst->code = (u_short)p->s.code;
  1871.     dst->k = p->s.k;
  1872.     if (JT(p)) {
  1873.         off = JT(p)->offset - (p->offset + slen) - 1;
  1874.         if (off >= 256)
  1875.             bpf_error("long jumps not supported");
  1876.         dst->jt = off;
  1877.         off = JF(p)->offset - (p->offset + slen) - 1;
  1878.         if (off >= 256)
  1879.             bpf_error("long jumps not supported");
  1880.         dst->jf = off;
  1881.     }
  1882. }
  1883.  
  1884.  
  1885. /*
  1886.  * Convert flowgraph intermediate representation to the
  1887.  * BPF array representation.  Set *lenp to the number of instructions.
  1888.  */
  1889. struct bpf_insn *
  1890. icode_to_fcode(root, lenp)
  1891.     struct block *root;
  1892.     int *lenp;
  1893. {
  1894.     int n;
  1895.     struct bpf_insn *fp;
  1896.  
  1897.     unMarkAll();
  1898.     n = *lenp = count_stmts(root);
  1899.  
  1900.     fp = (struct bpf_insn *)malloc(sizeof(*fp) * n);
  1901.     memset((char *)fp, 0, sizeof(*fp) * n);
  1902.     fstart = fp;
  1903.     ftail = fp + n;
  1904.  
  1905.     unMarkAll();
  1906.     convert_code_r(root);
  1907.  
  1908.     return fp;
  1909. }
  1910.  
  1911. #ifdef BDEBUG
  1912. opt_dump(root)
  1913.     struct block *root;
  1914. {
  1915.     struct bpf_program f;
  1916.  
  1917.     memset(bids, 0, sizeof bids);
  1918.     f.bf_insns = icode_to_fcode(root, &f.bf_len);
  1919.     bpf_dump(&f, 1);
  1920.     putchar('\n');
  1921.     free((char *)f.bf_insns);
  1922. }
  1923. #endif
  1924.